package com.example.Arithmetic.Arithmetic;

import java.util.LinkedList;
import java.util.List;

/**
 * 日期：2023/12/29
 * 时间：14:26
 * 描述：拓扑排序
 */
public class TopologicalSort {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("网页基础");
        Vertex v2 = new Vertex("Java基础");
        Vertex v3 = new Vertex("JavaWeb");
        Vertex v4 = new Vertex("Spring框架");
        Vertex v5 = new Vertex("微服务框架");
        Vertex v6 = new Vertex("数据库");
        Vertex v7 = new Vertex("实战项目");

        v1.edges = List.of(new Edge(v3)); // +1
        v2.edges = List.of(new Edge(v3)); // +1
        v3.edges = List.of(new Edge(v4));
        v6.edges = List.of(new Edge(v4));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of(new Edge(v7));
        v7.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
//        统计每个顶点的入度
        for (Vertex v : graph) {
            for (Edge e : v.edges) {
                e.linked.inDegree++;
            }
        }

//        遍历集合，将入度为零的顶点加入队列
        LinkedList<Vertex> queue = new LinkedList<>();
        for (Vertex v : graph) {
            if (v.inDegree == 0) {
                queue.offer(v);
            }
        }

//        遍历，相邻度数减一，等于零加入队列
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            System.out.println(poll.name);
            for (Edge e : poll.edges) {
                e.linked.inDegree--;
                if (e.linked.inDegree == 0) {
                    queue.offer(e.linked);
                }
            }
        }
    }
}
